package puzzle.projecteuler.p300;


public class Problem201 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();

		int k = 50;
		int min = 0;
		int max = 0;

		for (int i = 1; i <= k; i ++) {
			min += i*i;
			max += (i+k)*(i+k);
		}
		System.out.println(min);
		System.out.println(max);
		
//		long c = 0;
//		for (int n = min; n <= max; n ++) {
////			System.out.println(n);
//			if (count(n, k, 2*k) == 1) {
//				c ++;
//			}
//		}
		System.out.println(count(130424, k, 2*k));
//		System.out.println(c*(max+min)/2);
		System.out.println("Time: " + (System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * 判断返回从1^2, 2^2, ..., k^2中选择n个数，其和等于m的方法数是否多于1种
	 * @param m
	 * @param n
	 * @param k
	 * @return 返回0、1，表示方法数为0或1；返回2，则表示多于一种。
	 */
	public static int count(int m, int n, int k) {
		
//		System.out.println(m+","+n+","+k);
		if (n == 1) {
			if (m < 1) {
				return 0;
			} else {
				int t = (int)Math.sqrt(m);
				if (m == t*t && t <= k) {
					return 1;
				} else {
					return 0;
				}
			}
		} else if (n > k) {
			return 0;
		} else if (m < n*(n+1)*(2*n+1)/6) {
			return 0;
		} else if (m > k*(k+1)*(2*k+1)/6 - (k-n)*(k-n+1)*(2*(k-n)+1)/6) {
			return 0;
		} else {
			int c = 0;
			int t = Math.min((int)Math.sqrt(m), k);
			for (int x = t; x > 0; x --) {
				c += count(m-x*x, n-1, Math.min(x-1, (int)Math.sqrt(m-x*x)));
				if (c > 2) {
					return 2;
				}
			}
			return c;
		}
	}
}
